Complexité temporelle (Time Complexity) Elle ne mesure pas le temps absolu d'exécution d'un algorithme en secondes, mais plutôt une fonction mathématique décrivant comment le temps d'exécution augmente avec la taille du problème $n$. Elle repose sur le principe fondamental selon lequel l'analyse algorithmique est une mesure indépendante de l'implémentation.
Pourquoi est-elle un langage universel ?
- Évolution quantifiée: La notation O ignore les termes d'ordre inférieur et les constantes, se concentrant uniquement surOrdre de grandeur (Order of Magnitude).
- Détermination de la mesure: Les programmeurs adoptent généralement comme référenceCas le plus défavorable (Worst Case) comme base pour garantir un seuil minimal de performance.
- Décision indépendante de l'environnement: Que ce soit sur un supercalculateur ou une puce embarquée, l'amélioration de $O(n^2)$ à $O(n \log n)$ apporte un gain fondamental.
Méthode par comptage (Counting)
Calculer le nombre d'occurrences de chaque caractère dans deux chaînes. Si les listes de compte sont identiques, les deux chaînes sont nécessairement des anagrammes. Cette méthode atteint une efficacité de Comptage : $O(n)$ d'efficacité.